Proyecto final ADA 2023-1¶

Integrantes¶

  • Andrés Felipe Aparicio Mestre - anapariciom@unal.edu.co
  • Emmanuel López Rodríguez - emlopezr@unal.edu.co
  • Johan Madroñero Cuervo - jmadronero@unal.edu.co
  • Maria Paula Duque Muñoz - maduquem@unal.edu.co

Planteamiento¶

imagen_2023-06-21_143151613.png

Solución¶

Preprocesamiento de los datos¶

Inicialmente se consiguen las coordenadas de todos los circuitos del calendario 2023 de la Formula 1 (Incluyendo el "Autodromo Internazionale Enzo e Dino Ferrari" en Imola, ya que este año se canceló pero inicialmente hacía parte del calendario)

  • Los datos y el orden de los circuitos se pueden consultar en estos enlaces Wikipedia y Formula1.com

  • Se obtuvo la latitud y longitud de cada circuito usando la página GeoHack

Mediante la fórmula del semiverseno (Harvesine Formula) se calculan las distancias entre todos ellos y con ellas se construye un grafo representado en un diccionario de diccinarios.

$$d = 2R \, \arcsin \sqrt{\sin^{2} \frac{\varphi_{1} - \varphi_{2}}{2} + \cos\varphi_{1} \cos\varphi_{2} \sin^{2} \frac{\lambda_{1} - \lambda_{2}}{2}}$$

In [ ]:
from numpy import sqrt, sin, cos, arcsin, radians
from json import dumps # Para imprimir bien el grafo

circuits = [
    ('Bahrain International Circuit', 'Sakhir', 'Bahrain', 26.0325, 50.510556),
    ('Jeddah Corniche Circuit', 'Jeddah', 'Saudi Arabia', 21.631944, 39.104444),
    ('Albert Park Circuit', 'Melbourne', 'Australia', -37.849722, 144.968333),
    ('Baku City Circuit', 'Baku', 'Azerbaijan', 40.3725, 49.853333),
    ('Miami International Autodrome', 'Miami', 'United States', 25.958056, -80.238889),
    ('Autodromo Internazionale Enzo e Dino Ferrari', 'Imola', 'Italy', 44.341111, 11.713333),
    ('Circuit de Monaco', 'Montecarlo', 'Monaco', 43.734722, 7.420556),
    ('Circuit de Barcelona-Catalunya', 'Barcelona', 'Spain', 41.57, 2.261111),
    ('Circuit Gilles Villeneuve', 'Montreal', 'Canada', 45.500556, -73.5225),
    ('Red Bull Ring', 'Spielberg', 'Austria', 47.219722, 14.764722),
    ('Silverstone Circuit', 'Silverstone', 'United Kingdom', 52.078611, -1.016944),
    ('Hungaroring', 'Budapest', 'Hungary', 47.582222, 19.251111),
    ('Circuit de Spa-Francorchamps', 'Spa-Francorchamps', 'Belgium', 50.437222, 5.971389),
    ('Circuit Zandvoort', 'Zandvoort', 'Netherlands', 52.388819, 4.540922),
    ('Autodromo Nazionale di Monza', 'Monza', 'Italy', 45.620556, 9.289444),
    ('Marina Bay Street Circuit', 'Marina Bay', 'Singapore', 1.291531, 103.86385),
    ('Suzuka International Racing Course', 'Suzuka', 'Japan', 34.843056, 136.540556),
    ('Lusail International Circuit', 'Lusail', 'Qatar', 25.49, 51.454167),
    ('Circuit of the Americas', 'Austin', 'United States', 30.132778, -97.641111),
    ('Autódromo Hermanos Rodriguez', 'Mexico City', 'Mexico', 19.406111, -99.0925),
    ('Autódromo José Carlos Pace', 'Sao Paulo', 'Brazil', -23.701111, -46.697222),
    ('Las Vegas Strip Circuit', 'Las Vegas', 'United States', 36.119684, -115.172599),
    ('Yas Marina Circuit', 'Abu Dhabi', 'United Arab Emirates', 24.467222, 54.603056),
]

# Formula para calcular distancias con latitud y longitud (Haversine formula)
def haversineDistance(circuit1, circuit2):
    # d = 2R × sin⁻¹(√[sin²((θ₂ - θ₁)/2) + cosθ₁ × cosθ₂ × sin²((φ₂ - φ₁)/2)])

    # θ₁, φ₁ – lat1, lon1 -> Radians
    # θ₂, φ₂ – lat2, lon2 -> Radians
    # R – Radio de la tierra (R = 6371km)
    # d = Distancia en Km entre los dos puntos

    lat1, lon1 = radians(circuit1[3]), radians(circuit1[4])
    lat2, lon2 = radians(circuit2[3]), radians(circuit2[4])

    d = 2*6371 * arcsin(sqrt((sin((lat2 - lat1)/2)**2) + (cos(lat1) * cos(lat2) * (sin((lon2 - lon1)/2)**2))))

    return round(d, 2)


# Crear y rellenar el grafo con las distancias entre todos los circuitos
def generateGraph(circuits): #O(N^2)
    graph = {circuit[1]: {} for circuit in circuits}

    for circuit1 in circuits:
        city1 = circuit1[1]

        # Calcular distancias con cada uno de los otros circuitos
        for circuit2 in circuits:
            city2 = circuit2[1]

            # Poner un infinito como distancia a sí mismo
            if city1 == city2:
                graph[city1][city2] = float('inf')
                continue

            d = haversineDistance(circuit1, circuit2)
            graph[city1][city2], graph[city2][city1] = d, d

    return graph

graph = generateGraph(circuits)

print(dumps(graph, indent=4))
{
    "Sakhir": {
        "Sakhir": Infinity,
        "Jeddah": 1258.42,
        "Melbourne": 12112.65,
        "Baku": 1595.69,
        "Miami": 12185.61,
        "Imola": 4018.42,
        "Montecarlo": 4332.64,
        "Barcelona": 4710.92,
        "Montreal": 10258.89,
        "Spielberg": 3910.83,
        "Silverstone": 5158.07,
        "Budapest": 3629.0,
        "Spa-Francorchamps": 4640.38,
        "Zandvoort": 4805.04,
        "Monza": 4242.25,
        "Marina Bay": 6327.17,
        "Suzuka": 8054.3,
        "Lusail": 112.11,
        "Austin": 12908.76,
        "Mexico City": 13990.04,
        "Sao Paulo": 11813.24,
        "Las Vegas": 12942.72,
        "Abu Dhabi": 446.84
    },
    "Jeddah": {
        "Sakhir": 1258.42,
        "Jeddah": Infinity,
        "Melbourne": 12817.13,
        "Baku": 2317.67,
        "Miami": 11605.61,
        "Imola": 3559.52,
        "Montecarlo": 3810.51,
        "Barcelona": 4087.37,
        "Montreal": 9929.36,
        "Spielberg": 3585.07,
        "Silverstone": 4815.75,
        "Budapest": 3387.96,
        "Spa-Francorchamps": 4307.68,
        "Zandvoort": 4515.09,
        "Monza": 3797.32,
        "Marina Bay": 7353.78,
        "Suzuka": 9293.26,
        "Lusail": 1329.12,
        "Austin": 12632.6,
        "Mexico City": 13574.55,
        "Sao Paulo": 10555.29,
        "Las Vegas": 13046.96,
        "Abu Dhabi": 1615.84
    },
    "Melbourne": {
        "Sakhir": 12112.65,
        "Jeddah": 12817.13,
        "Melbourne": Infinity,
        "Baku": 12989.09,
        "Miami": 15594.44,
        "Imola": 16086.6,
        "Montecarlo": 16422.24,
        "Barcelona": 16823.36,
        "Montreal": 16741.08,
        "Spielberg": 15878.76,
        "Silverstone": 16947.24,
        "Budapest": 15546.29,
        "Spa-Francorchamps": 16511.75,
        "Zandvoort": 16572.56,
        "Monza": 16287.46,
        "Marina Bay": 6057.73,
        "Suzuka": 8129.71,
        "Lusail": 12000.57,
        "Austin": 14286.03,
        "Mexico City": 13563.72,
        "Sao Paulo": 13063.22,
        "Las Vegas": 13131.4,
        "Abu Dhabi": 11674.78
    },
    "Baku": {
        "Sakhir": 1595.69,
        "Jeddah": 2317.67,
        "Melbourne": 12989.09,
        "Baku": Infinity,
        "Miami": 11015.92,
        "Imola": 3136.08,
        "Montecarlo": 3484.88,
        "Barcelona": 3946.5,
        "Montreal": 8930.46,
        "Spielberg": 2890.54,
        "Silverstone": 4030.59,
        "Budapest": 2557.24,
        "Spa-Francorchamps": 3545.36,
        "Zandvoort": 3652.58,
        "Monza": 3313.73,
        "Marina Bay": 6946.61,
        "Suzuka": 7342.51,
        "Lusail": 1661.5,
        "Austin": 11489.36,
        "Mexico City": 12631.8,
        "Sao Paulo": 12217.45,
        "Las Vegas": 11372.96,
        "Abu Dhabi": 1823.13
    },
    "Miami": {
        "Sakhir": 12185.61,
        "Jeddah": 11605.61,
        "Melbourne": 15594.44,
        "Baku": 11015.92,
        "Miami": Infinity,
        "Imola": 8172.77,
        "Montecarlo": 7870.82,
        "Barcelona": 7536.28,
        "Montreal": 2253.95,
        "Spielberg": 8278.96,
        "Silverstone": 7043.57,
        "Budapest": 8573.81,
        "Spa-Francorchamps": 7556.52,
        "Zandvoort": 7408.91,
        "Monza": 7945.63,
        "Marina Bay": 16953.17,
        "Suzuka": 12224.23,
        "Lusail": 12295.51,
        "Austin": 1767.7,
        "Mexico City": 2064.2,
        "Sao Paulo": 6596.07,
        "Las Vegas": 3492.79,
        "Abu Dhabi": 12600.08
    },
    "Imola": {
        "Sakhir": 4018.42,
        "Jeddah": 3559.52,
        "Melbourne": 16086.6,
        "Baku": 3136.08,
        "Miami": 8172.77,
        "Imola": Infinity,
        "Montecarlo": 349.66,
        "Barcelona": 828.03,
        "Montreal": 6372.16,
        "Spielberg": 397.99,
        "Silverstone": 1273.43,
        "Budapest": 684.63,
        "Spa-Francorchamps": 803.4,
        "Zandvoort": 1038.81,
        "Monza": 237.86,
        "Marina Bay": 10078.12,
        "Suzuka": 9598.9,
        "Lusail": 4129.41,
        "Austin": 9074.85,
        "Mexico City": 10054.55,
        "Sao Paulo": 9611.69,
        "Las Vegas": 9591.62,
        "Abu Dhabi": 4444.1
    },
    "Montecarlo": {
        "Sakhir": 4332.64,
        "Jeddah": 3810.51,
        "Melbourne": 16422.24,
        "Baku": 3484.88,
        "Miami": 7870.82,
        "Imola": 349.66,
        "Montecarlo": Infinity,
        "Barcelona": 485.64,
        "Montreal": 6121.68,
        "Spielberg": 690.95,
        "Silverstone": 1119.23,
        "Budapest": 1012.7,
        "Spa-Francorchamps": 753.28,
        "Zandvoort": 985.59,
        "Monza": 256.51,
        "Marina Bay": 10425.03,
        "Suzuka": 9874.92,
        "Lusail": 4444.16,
        "Austin": 8824.29,
        "Mexico City": 9778.17,
        "Sao Paulo": 9305.99,
        "Las Vegas": 9413.47,
        "Abu Dhabi": 4763.02
    },
    "Barcelona": {
        "Sakhir": 4710.92,
        "Jeddah": 4087.37,
        "Melbourne": 16823.36,
        "Baku": 3946.5,
        "Miami": 7536.28,
        "Imola": 828.03,
        "Montecarlo": 485.64,
        "Barcelona": Infinity,
        "Montreal": 5891.46,
        "Spielberg": 1173.28,
        "Silverstone": 1194.5,
        "Budapest": 1498.27,
        "Spa-Francorchamps": 1026.45,
        "Zandvoort": 1215.2,
        "Monza": 722.86,
        "Marina Bay": 10873.33,
        "Suzuka": 10323.58,
        "Lusail": 4822.98,
        "Austin": 8582.42,
        "Mexico City": 9487.4,
        "Sao Paulo": 8834.48,
        "Las Vegas": 9287.99,
        "Abu Dhabi": 5148.62
    },
    "Montreal": {
        "Sakhir": 10258.89,
        "Jeddah": 9929.36,
        "Melbourne": 16741.08,
        "Baku": 8930.46,
        "Miami": 2253.95,
        "Imola": 6372.16,
        "Montecarlo": 6121.68,
        "Barcelona": 5891.46,
        "Montreal": Infinity,
        "Spielberg": 6390.43,
        "Silverstone": 5137.16,
        "Budapest": 6644.58,
        "Spa-Francorchamps": 5654.94,
        "Zandvoort": 5470.17,
        "Monza": 6134.8,
        "Marina Bay": 14805.68,
        "Suzuka": 10583.98,
        "Lusail": 10362.75,
        "Austin": 2703.24,
        "Mexico City": 3731.52,
        "Sao Paulo": 8159.53,
        "Las Vegas": 3612.48,
        "Abu Dhabi": 10635.83
    },
    "Spielberg": {
        "Sakhir": 3910.83,
        "Jeddah": 3585.07,
        "Melbourne": 15878.76,
        "Baku": 2890.54,
        "Miami": 8278.96,
        "Imola": 397.99,
        "Montecarlo": 690.95,
        "Barcelona": 1173.28,
        "Montreal": 6390.43,
        "Spielberg": Infinity,
        "Silverstone": 1254.64,
        "Budapest": 340.01,
        "Spa-Francorchamps": 735.75,
        "Zandvoort": 930.58,
        "Monza": 455.69,
        "Marina Bay": 9834.11,
        "Suzuka": 9203.96,
        "Lusail": 4019.63,
        "Austin": 9083.34,
        "Mexico City": 10104.57,
        "Sao Paulo": 9994.29,
        "Las Vegas": 9494.42,
        "Abu Dhabi": 4321.12
    },
    "Silverstone": {
        "Sakhir": 5158.07,
        "Jeddah": 4815.75,
        "Melbourne": 16947.24,
        "Baku": 4030.59,
        "Miami": 7043.57,
        "Imola": 1273.43,
        "Montecarlo": 1119.23,
        "Barcelona": 1194.5,
        "Montreal": 5137.16,
        "Spielberg": 1254.64,
        "Silverstone": Infinity,
        "Budapest": 1531.29,
        "Spa-Francorchamps": 519.16,
        "Zandvoort": 379.97,
        "Monza": 1039.49,
        "Marina Bay": 10902.48,
        "Suzuka": 9507.07,
        "Lusail": 5265.9,
        "Austin": 7833.24,
        "Mexico City": 8850.1,
        "Sao Paulo": 9522.4,
        "Las Vegas": 8319.6,
        "Abu Dhabi": 5561.33
    },
    "Budapest": {
        "Sakhir": 3629.0,
        "Jeddah": 3387.96,
        "Melbourne": 15546.29,
        "Baku": 2557.24,
        "Miami": 8573.81,
        "Imola": 684.63,
        "Montecarlo": 1012.7,
        "Barcelona": 1498.27,
        "Montreal": 6644.58,
        "Spielberg": 340.01,
        "Silverstone": 1531.29,
        "Budapest": Infinity,
        "Spa-Francorchamps": 1017.62,
        "Zandvoort": 1176.78,
        "Monza": 791.06,
        "Marina Bay": 9497.62,
        "Suzuka": 8932.35,
        "Lusail": 3736.24,
        "Austin": 9326.25,
        "Mexico City": 10369.32,
        "Sao Paulo": 10294.49,
        "Las Vegas": 9664.72,
        "Abu Dhabi": 4030.08
    },
    "Spa-Francorchamps": {
        "Sakhir": 4640.38,
        "Jeddah": 4307.68,
        "Melbourne": 16511.75,
        "Baku": 3545.36,
        "Miami": 7556.52,
        "Imola": 803.4,
        "Montecarlo": 753.28,
        "Barcelona": 1026.45,
        "Montreal": 5654.94,
        "Spielberg": 735.75,
        "Silverstone": 519.16,
        "Budapest": 1017.62,
        "Spa-Francorchamps": Infinity,
        "Zandvoort": 238.6,
        "Monza": 589.54,
        "Marina Bay": 10454.26,
        "Suzuka": 9366.27,
        "Lusail": 4748.49,
        "Austin": 8349.21,
        "Mexico City": 9369.25,
        "Sao Paulo": 9728.52,
        "Las Vegas": 8800.37,
        "Abu Dhabi": 5045.71
    },
    "Zandvoort": {
        "Sakhir": 4805.04,
        "Jeddah": 4515.09,
        "Melbourne": 16572.56,
        "Baku": 3652.58,
        "Miami": 7408.91,
        "Imola": 1038.81,
        "Montecarlo": 985.59,
        "Barcelona": 1215.2,
        "Montreal": 5470.17,
        "Spielberg": 930.58,
        "Silverstone": 379.97,
        "Budapest": 1176.78,
        "Spa-Francorchamps": 238.6,
        "Zandvoort": Infinity,
        "Monza": 828.04,
        "Marina Bay": 10524.08,
        "Suzuka": 9257.63,
        "Lusail": 4911.88,
        "Austin": 8157.69,
        "Mexico City": 9192.85,
        "Sao Paulo": 9807.17,
        "Las Vegas": 8577.34,
        "Abu Dhabi": 5202.6
    },
    "Monza": {
        "Sakhir": 4242.25,
        "Jeddah": 3797.32,
        "Melbourne": 16287.46,
        "Baku": 3313.73,
        "Miami": 7945.63,
        "Imola": 237.86,
        "Montecarlo": 256.51,
        "Barcelona": 722.86,
        "Montreal": 6134.8,
        "Spielberg": 455.69,
        "Silverstone": 1039.49,
        "Budapest": 791.06,
        "Spa-Francorchamps": 589.54,
        "Zandvoort": 828.04,
        "Monza": Infinity,
        "Marina Bay": 10260.26,
        "Suzuka": 9619.4,
        "Lusail": 4352.89,
        "Austin": 8837.36,
        "Mexico City": 9819.9,
        "Sao Paulo": 9555.17,
        "Las Vegas": 9359.03,
        "Abu Dhabi": 4664.98
    },
    "Marina Bay": {
        "Sakhir": 6327.17,
        "Jeddah": 7353.78,
        "Melbourne": 6057.73,
        "Baku": 6946.61,
        "Miami": 16953.17,
        "Imola": 10078.12,
        "Montecarlo": 10425.03,
        "Barcelona": 10873.33,
        "Montreal": 14805.68,
        "Spielberg": 9834.11,
        "Silverstone": 10902.48,
        "Budapest": 9497.62,
        "Spa-Francorchamps": 10454.26,
        "Zandvoort": 10524.08,
        "Monza": 10260.26,
        "Marina Bay": Infinity,
        "Suzuka": 5035.94,
        "Lusail": 6219.23,
        "Austin": 15843.03,
        "Mexico City": 16612.99,
        "Sao Paulo": 15982.53,
        "Las Vegas": 14219.52,
        "Abu Dhabi": 5882.31
    },
    "Suzuka": {
        "Sakhir": 8054.3,
        "Jeddah": 9293.26,
        "Melbourne": 8129.71,
        "Baku": 7342.51,
        "Miami": 12224.23,
        "Imola": 9598.9,
        "Montecarlo": 9874.92,
        "Barcelona": 10323.58,
        "Montreal": 10583.98,
        "Spielberg": 9203.96,
        "Silverstone": 9507.07,
        "Budapest": 8932.35,
        "Spa-Francorchamps": 9366.27,
        "Zandvoort": 9257.63,
        "Monza": 9619.4,
        "Marina Bay": 5035.94,
        "Suzuka": Infinity,
        "Lusail": 8003.94,
        "Austin": 10829.02,
        "Mexico City": 11598.54,
        "Sao Paulo": 18737.21,
        "Las Vegas": 9184.92,
        "Abu Dhabi": 7787.84
    },
    "Lusail": {
        "Sakhir": 112.11,
        "Jeddah": 1329.12,
        "Melbourne": 12000.57,
        "Baku": 1661.5,
        "Miami": 12295.51,
        "Imola": 4129.41,
        "Montecarlo": 4444.16,
        "Barcelona": 4822.98,
        "Montreal": 10362.75,
        "Spielberg": 4019.63,
        "Silverstone": 5265.9,
        "Budapest": 3736.24,
        "Spa-Francorchamps": 4748.49,
        "Zandvoort": 4911.88,
        "Monza": 4352.89,
        "Marina Bay": 6219.23,
        "Suzuka": 8003.94,
        "Lusail": Infinity,
        "Austin": 13008.45,
        "Mexico City": 14094.18,
        "Sao Paulo": 11883.26,
        "Las Vegas": 13022.06,
        "Abu Dhabi": 337.14
    },
    "Austin": {
        "Sakhir": 12908.76,
        "Jeddah": 12632.6,
        "Melbourne": 14286.03,
        "Baku": 11489.36,
        "Miami": 1767.7,
        "Imola": 9074.85,
        "Montecarlo": 8824.29,
        "Barcelona": 8582.42,
        "Montreal": 2703.24,
        "Spielberg": 9083.34,
        "Silverstone": 7833.24,
        "Budapest": 9326.25,
        "Spa-Francorchamps": 8349.21,
        "Zandvoort": 8157.69,
        "Monza": 8837.36,
        "Marina Bay": 15843.03,
        "Suzuka": 10829.02,
        "Lusail": 13008.45,
        "Austin": Infinity,
        "Mexico City": 1201.68,
        "Sao Paulo": 8085.15,
        "Las Vegas": 1759.74,
        "Abu Dhabi": 13260.62
    },
    "Mexico City": {
        "Sakhir": 13990.04,
        "Jeddah": 13574.55,
        "Melbourne": 13563.72,
        "Baku": 12631.8,
        "Miami": 2064.2,
        "Imola": 10054.55,
        "Montecarlo": 9778.17,
        "Barcelona": 9487.4,
        "Montreal": 3731.52,
        "Spielberg": 10104.57,
        "Silverstone": 8850.1,
        "Budapest": 10369.32,
        "Spa-Francorchamps": 9369.25,
        "Zandvoort": 9192.85,
        "Monza": 9819.9,
        "Marina Bay": 16612.99,
        "Suzuka": 11598.54,
        "Lusail": 14094.18,
        "Austin": 1201.68,
        "Mexico City": Infinity,
        "Sao Paulo": 7431.29,
        "Las Vegas": 2433.3,
        "Abu Dhabi": 14365.97
    },
    "Sao Paulo": {
        "Sakhir": 11813.24,
        "Jeddah": 10555.29,
        "Melbourne": 13063.22,
        "Baku": 12217.45,
        "Miami": 6596.07,
        "Imola": 9611.69,
        "Montecarlo": 9305.99,
        "Barcelona": 8834.48,
        "Montreal": 8159.53,
        "Spielberg": 9994.29,
        "Silverstone": 9522.4,
        "Budapest": 10294.49,
        "Spa-Francorchamps": 9728.52,
        "Zandvoort": 9807.17,
        "Monza": 9555.17,
        "Marina Bay": 15982.53,
        "Suzuka": 18737.21,
        "Lusail": 11883.26,
        "Austin": 8085.15,
        "Mexico City": 7431.29,
        "Sao Paulo": Infinity,
        "Las Vegas": 9788.14,
        "Abu Dhabi": 12148.74
    },
    "Las Vegas": {
        "Sakhir": 12942.72,
        "Jeddah": 13046.96,
        "Melbourne": 13131.4,
        "Baku": 11372.96,
        "Miami": 3492.79,
        "Imola": 9591.62,
        "Montecarlo": 9413.47,
        "Barcelona": 9287.99,
        "Montreal": 3612.48,
        "Spielberg": 9494.42,
        "Silverstone": 8319.6,
        "Budapest": 9664.72,
        "Spa-Francorchamps": 8800.37,
        "Zandvoort": 8577.34,
        "Monza": 9359.03,
        "Marina Bay": 14219.52,
        "Suzuka": 9184.92,
        "Lusail": 13022.06,
        "Austin": 1759.74,
        "Mexico City": 2433.3,
        "Sao Paulo": 9788.14,
        "Las Vegas": Infinity,
        "Abu Dhabi": 13193.06
    },
    "Abu Dhabi": {
        "Sakhir": 446.84,
        "Jeddah": 1615.84,
        "Melbourne": 11674.78,
        "Baku": 1823.13,
        "Miami": 12600.08,
        "Imola": 4444.1,
        "Montecarlo": 4763.02,
        "Barcelona": 5148.62,
        "Montreal": 10635.83,
        "Spielberg": 4321.12,
        "Silverstone": 5561.33,
        "Budapest": 4030.08,
        "Spa-Francorchamps": 5045.71,
        "Zandvoort": 5202.6,
        "Monza": 4664.98,
        "Marina Bay": 5882.31,
        "Suzuka": 7787.84,
        "Lusail": 337.14,
        "Austin": 13260.62,
        "Mexico City": 14365.97,
        "Sao Paulo": 12148.74,
        "Las Vegas": 13193.06,
        "Abu Dhabi": Infinity
    }
}

Cálculo de la distancia recorrida actual¶

In [ ]:
# Distancia recorrida actual en kilometros
currentTotalDistance = 0

for i in range(1, len(circuits)):
    currentTotalDistance += haversineDistance(circuits[i-1], circuits[i])

print(f'Total recorrido: {round(currentTotalDistance, 2)} Km')
Total recorrido: 132163.47 Km

Solución inical (Algoritmo greedy)¶

En primer lugar se realiza una aproximación greedy al problema. Por lo que se convierte el grafo en una representación matricial y la solución inicial consiste en elegir por cada fila la distancia más cercana a recorrer en el próximo paso.

In [ ]:
from prettytable import PrettyTable # Para imprimir bien la matriz

# Se usará una matriz en vez del diccionario de diccionarios
matrix = [list(j.values()) for (_, j) in graph.items()]

p = PrettyTable()
for row in matrix: p.add_row(row)

print(p.get_string(header=False, border=False))
   inf     1258.42   12112.65  1595.69   12185.61  4018.42   4332.64   4710.92   10258.89  3910.83   5158.07    3629.0   4640.38   4805.04   4242.25   6327.17    8054.3    112.11   12908.76  13990.04  11813.24  12942.72   446.84  
 1258.42     inf     12817.13  2317.67   11605.61  3559.52   3810.51   4087.37   9929.36   3585.07   4815.75   3387.96   4307.68   4515.09   3797.32   7353.78   9293.26   1329.12   12632.6   13574.55  10555.29  13046.96  1615.84  
 12112.65  12817.13    inf     12989.09  15594.44  16086.6   16422.24  16823.36  16741.08  15878.76  16947.24  15546.29  16511.75  16572.56  16287.46  6057.73   8129.71   12000.57  14286.03  13563.72  13063.22  13131.4   11674.78 
 1595.69   2317.67   12989.09    inf     11015.92  3136.08   3484.88    3946.5   8930.46   2890.54   4030.59   2557.24   3545.36   3652.58   3313.73   6946.61   7342.51    1661.5   11489.36  12631.8   12217.45  11372.96  1823.13  
 12185.61  11605.61  15594.44  11015.92    inf     8172.77   7870.82   7536.28   2253.95   8278.96   7043.57   8573.81   7556.52   7408.91   7945.63   16953.17  12224.23  12295.51   1767.7    2064.2   6596.07   3492.79   12600.08 
 4018.42   3559.52   16086.6   3136.08   8172.77     inf      349.66    828.03   6372.16    397.99   1273.43    684.63    803.4    1038.81    237.86   10078.12   9598.9   4129.41   9074.85   10054.55  9611.69   9591.62    4444.1  
 4332.64   3810.51   16422.24  3484.88   7870.82    349.66     inf      485.64   6121.68    690.95   1119.23    1012.7    753.28    985.59    256.51   10425.03  9874.92   4444.16   8824.29   9778.17   9305.99   9413.47   4763.02  
 4710.92   4087.37   16823.36   3946.5   7536.28    828.03    485.64     inf     5891.46   1173.28    1194.5   1498.27   1026.45    1215.2    722.86   10873.33  10323.58  4822.98   8582.42    9487.4   8834.48   9287.99   5148.62  
 10258.89  9929.36   16741.08  8930.46   2253.95   6372.16   6121.68   5891.46     inf     6390.43   5137.16   6644.58   5654.94   5470.17    6134.8   14805.68  10583.98  10362.75  2703.24   3731.52   8159.53   3612.48   10635.83 
 3910.83   3585.07   15878.76  2890.54   8278.96    397.99    690.95   1173.28   6390.43     inf     1254.64    340.01    735.75    930.58    455.69   9834.11   9203.96   4019.63   9083.34   10104.57  9994.29   9494.42   4321.12  
 5158.07   4815.75   16947.24  4030.59   7043.57   1273.43   1119.23    1194.5   5137.16   1254.64     inf     1531.29    519.16    379.97   1039.49   10902.48  9507.07    5265.9   7833.24    8850.1    9522.4    8319.6   5561.33  
  3629.0   3387.96   15546.29  2557.24   8573.81    684.63    1012.7   1498.27   6644.58    340.01   1531.29     inf     1017.62   1176.78    791.06   9497.62   8932.35   3736.24   9326.25   10369.32  10294.49  9664.72   4030.08  
 4640.38   4307.68   16511.75  3545.36   7556.52    803.4     753.28   1026.45   5654.94    735.75    519.16   1017.62     inf      238.6     589.54   10454.26  9366.27   4748.49   8349.21   9369.25   9728.52   8800.37   5045.71  
 4805.04   4515.09   16572.56  3652.58   7408.91   1038.81    985.59    1215.2   5470.17    930.58    379.97   1176.78    238.6      inf      828.04   10524.08  9257.63   4911.88   8157.69   9192.85   9807.17   8577.34    5202.6  
 4242.25   3797.32   16287.46  3313.73   7945.63    237.86    256.51    722.86    6134.8    455.69   1039.49    791.06    589.54    828.04     inf     10260.26   9619.4   4352.89   8837.36    9819.9   9555.17   9359.03   4664.98  
 6327.17   7353.78   6057.73   6946.61   16953.17  10078.12  10425.03  10873.33  14805.68  9834.11   10902.48  9497.62   10454.26  10524.08  10260.26    inf     5035.94   6219.23   15843.03  16612.99  15982.53  14219.52  5882.31  
  8054.3   9293.26   8129.71   7342.51   12224.23   9598.9   9874.92   10323.58  10583.98  9203.96   9507.07   8932.35   9366.27   9257.63    9619.4   5035.94     inf     8003.94   10829.02  11598.54  18737.21  9184.92   7787.84  
  112.11   1329.12   12000.57   1661.5   12295.51  4129.41   4444.16   4822.98   10362.75  4019.63    5265.9   3736.24   4748.49   4911.88   4352.89   6219.23   8003.94     inf     13008.45  14094.18  11883.26  13022.06   337.14  
 12908.76  12632.6   14286.03  11489.36   1767.7   9074.85   8824.29   8582.42   2703.24   9083.34   7833.24   9326.25   8349.21   8157.69   8837.36   15843.03  10829.02  13008.45    inf     1201.68   8085.15   1759.74   13260.62 
 13990.04  13574.55  13563.72  12631.8    2064.2   10054.55  9778.17    9487.4   3731.52   10104.57   8850.1   10369.32  9369.25   9192.85    9819.9   16612.99  11598.54  14094.18  1201.68     inf     7431.29    2433.3   14365.97 
 11813.24  10555.29  13063.22  12217.45  6596.07   9611.69   9305.99   8834.48   8159.53   9994.29    9522.4   10294.49  9728.52   9807.17   9555.17   15982.53  18737.21  11883.26  8085.15   7431.29     inf     9788.14   12148.74 
 12942.72  13046.96  13131.4   11372.96  3492.79   9591.62   9413.47   9287.99   3612.48   9494.42    8319.6   9664.72   8800.37   8577.34   9359.03   14219.52  9184.92   13022.06  1759.74    2433.3   9788.14     inf     13193.06 
  446.84   1615.84   11674.78  1823.13   12600.08   4444.1   4763.02   5148.62   10635.83  4321.12   5561.33   4030.08   5045.71    5202.6   4664.98   5882.31   7787.84    337.14   13260.62  14365.97  12148.74  13193.06    inf    
In [ ]:
def greedyRoute(graph, firstCity): # O(N^2)
    # Conseguir la matriz a partir del diccionario de diccionarios
    matrix = [list(j.values()) for (_, j) in graph.items()] #O(N)

    totalDistance = 0
    route = []

    # Tener en cuenta la primera ciudad
    currentCity = firstCity
    route.append(currentCity)

    while len(route) < len(graph):
        # Se busca la mínima distancia a la próxima ciudad disponible
        minDistance = min(matrix[currentCity])
        nextCity = matrix[currentCity].index(minDistance)

        # Sumar la distancia a recorrer al total recorrido
        totalDistance += minDistance

        # Como ya se visitó la ciudad actual, se hace "inaccesible"
        for row in range(len(matrix)):
            matrix[row][currentCity] = float('inf')

        # Se visita la siguiente ciudad y se repite el mismo proceso
        route.append(nextCity)
        currentCity = nextCity

    return totalDistance, route

# Probar el algoritmo usando como punto de partida cada ciudad y buscar el menor
bestDistance, bestRoute = float('inf'), []

for i in range(len(graph)): # O(N^3)
    distance, route = greedyRoute(graph, i)

    if distance < bestDistance:
        bestDistance, bestRoute = distance, route

# Imprimir los resultados
print(f'Total recorrido: {round(bestDistance, 2)} Km')
print(f'Mejora con respecto al actual: {round(((currentTotalDistance-bestDistance)/currentTotalDistance)*100, 2)}%')

print('\nRuta:')
for i, city in enumerate(bestRoute):
    print(f'{i+1}. {circuits[city][1]}, {circuits[city][2]}')
Total recorrido: 51280.4 Km
Mejora con respecto al actual: 61.2%

Ruta:
1. Sao Paulo, Brazil
2. Miami, United States
3. Austin, United States
4. Mexico City, Mexico
5. Las Vegas, United States
6. Montreal, Canada
7. Silverstone, United Kingdom
8. Zandvoort, Netherlands
9. Spa-Francorchamps, Belgium
10. Monza, Italy
11. Imola, Italy
12. Montecarlo, Monaco
13. Barcelona, Spain
14. Spielberg, Austria
15. Budapest, Hungary
16. Baku, Azerbaijan
17. Sakhir, Bahrain
18. Lusail, Qatar
19. Abu Dhabi, United Arab Emirates
20. Jeddah, Saudi Arabia
21. Marina Bay, Singapore
22. Suzuka, Japan
23. Melbourne, Australia

Se observa que esta aproximación disminuye la distancia total recorrida comparado con la actual en un 61.2%, pero esta aproximación no es totalmente óptima, por lo que en los lugares aledaños a los "problemáticos" se opta por calcular la organización de estos nodos usando búsqueda exhaustiva

imagen_2023-06-21_142200636.png

Mejoramiento de la solución usando búsqueda exhaustiva¶

Nodos 1-6 (América)¶

En primer lugar, se identifica un potencial de mejoramiento en el recorrido de los nodos del continente americano (Nodos 1-6). Actualmente se recorren de esta manera:

  1. Sao Paulo, Brazil
  2. Miami, United States
  3. Austin, United States
  4. Mexico City, Mexico
  5. Las Vegas, United States
  6. Montreal, Canada

Como en este cruce entran en juego 6 nodos, es posible permitirse usar búsqueda exhaustiva para buscar la mejor solución, ya que hay solo 720 combinaciones posibles.

imagen_2023-06-21_225355878.png

In [ ]:
from itertools import permutations

circuits1 = [
    ('Autódromo José Carlos Pace', 'Sao Paulo', 'Brazil', -23.701111, -46.697222),
    ('Miami International Autodrome', 'Miami', 'United States', 25.958056, -80.238889),
    ('Circuit of the Americas', 'Austin', 'United States', 30.132778, -97.641111),
    ('Autódromo Hermanos Rodriguez', 'Mexico City', 'Mexico', 19.406111, -99.0925),
    ('Las Vegas Strip Circuit', 'Las Vegas', 'United States', 36.119684, -115.172599),
    ('Circuit Gilles Villeneuve', 'Montreal', 'Canada', 45.500556, -73.5225),
]

# Distancia recorrida actual de esos nodos
currentDistance = 0

for i in range(1, len(circuits1)):
    currentDistance += haversineDistance(circuits1[i-1], circuits1[i])

# Generar todos los posibles recorridos
array = [i for i in range(len(circuits1))]
perms = permutations(array)

# Solo se necesitan los recorridos que empiezan en Sao Paulo y terminan en Montreal
perms = list(filter(lambda i: i[0] == 0 and i[-1] == 5, perms))
print(f'Complejidad: {len(perms)} posibles soluciones\n')

# Hacer la búsqueda exhaustiva buscando la ruta más corta
bestDistance, bestRoute = float('inf'), []

for perm in perms:
    distance = 0

    for i in range(1, len(perm)):
        distance += haversineDistance(circuits1[perm[i-1]], circuits1[perm[i]])

    if distance < bestDistance:
        bestDistance, bestRoute = distance, perm

# Imprimir los resultados
print(f'Total recorrido actual: {round(currentDistance, 2)} Km')
print(f'Total recorrido óptimo: {round(bestDistance, 2)} Km')
print(f'Mejora con respecto al actual: {round(((currentDistance-bestDistance)/currentDistance)*100, 2)}%')

print('\nRuta:')
for i, city in enumerate(bestRoute):
    print(f'{i+1}. {circuits1[city][1]}, {circuits1[city][2]}')
Complejidad: 24 posibles soluciones

Total recorrido actual: 15611.23 Km
Total recorrido óptimo: 15234.17 Km
Mejora con respecto al actual: 2.42%

Ruta:
1. Sao Paulo, Brazil
2. Miami, United States
3. Mexico City, Mexico
4. Austin, United States
5. Las Vegas, United States
6. Montreal, Canada

Nodos 9-14 (Europa)¶

Este es el punto más crítico ya que al recorrer los nodos 9-14 se crea un cruce, que indica que este sub-recorrido no es óptimo.

  1. Spa-Francorchamps, Belgium
  2. Monza, Italy
  3. Imola, Italy
  4. Montecarlo, Monaco
  5. Barcelona, Spain
  6. Spielberg, Austria

Como en este cruce entran en juego 6 nodos, se puede permitir usar búsqueda exhaustiva para buscar la mejor solución, ya que hay solo 720 combinaciones posibles.

imagen_2023-06-21_215836978.png

In [ ]:
from itertools import permutations

circuits1 = [
    ('Circuit de Spa-Francorchamps', 'Spa-Francorchamps', 'Belgium', 50.437222, 5.971389),
    ('Autodromo Nazionale di Monza', 'Monza', 'Italy', 45.620556, 9.289444),
    ('Autodromo Internazionale Enzo e Dino Ferrari', 'Imola', 'Italy', 44.341111, 11.713333),
    ('Circuit de Monaco', 'Montecarlo', 'Monaco', 43.734722, 7.420556),
    ('Circuit de Barcelona-Catalunya', 'Barcelona', 'Spain', 41.57, 2.261111),
    ('Red Bull Ring', 'Spielberg', 'Austria', 47.219722, 14.764722),
]
# Distancia recorrida actual de esos nodos
currentDistance = 0

for i in range(1, len(circuits1)):
    currentDistance += haversineDistance(circuits1[i-1], circuits1[i])


# Generar todos los posibles recorridos
array = [i for i in range(len(circuits1))]
perms = permutations(array)

# Solo se necesitan los recorridos que empiezan en Spa-Francorchamps y terminan en Spielberg
perms = list(filter(lambda i: i[0] == 0 and i[-1] == 5, perms))
print(f'Complejidad: {len(perms)} posibles soluciones\n')

# Hacer la búsqueda exhaustiva buscando la ruta más corta
bestDistance, bestRoute = float('inf'), []

for perm in perms:
    distance = 0

    for i in range(1, len(perm)):
        distance += haversineDistance(circuits1[perm[i-1]], circuits1[perm[i]])

    if distance < bestDistance:
        bestDistance, bestRoute = distance, perm

# Imprimir los resultados
print(f'Total recorrido actual: {round(currentDistance, 2)} Km')
print(f'Total recorrido óptimo: {round(bestDistance, 2)} Km')
print(f'Mejora con respecto al actual: {round(((currentDistance-bestDistance)/currentDistance)*100, 2)}%')

print('\nRuta:')
for i, city in enumerate(bestRoute):
    print(f'{i+9}. {circuits1[city][1]}, {circuits1[city][2]}')
Complejidad: 24 posibles soluciones

Total recorrido actual: 2835.98 Km
Total recorrido óptimo: 2404.45 Km
Mejora con respecto al actual: 15.22%

Ruta:
9. Spa-Francorchamps, Belgium
10. Barcelona, Spain
11. Montecarlo, Monaco
12. Monza, Italy
13. Imola, Italy
14. Spielberg, Austria

Nodos 16-21 (Medio Oriente)¶

Similar al caso anterior, aunque sin un cruce, notamos potencial de mejora en ese subconjunto del recorrido

  1. Baku, Azerbaijan
  2. Sakhir, Bahrain
  3. Lusail, Qatar
  4. Abu Dhabi, United Arab Emirates
  5. Jeddah, Saudi Arabia
  6. Marina Bay, Singapore

Como en este cruce entran en juego 6 nodos, se puede permitir usar búsqueda exhaustiva para buscar la mejor solución, ya que hay solo 720 combinaciones posibles.

imagen_2023-06-21_224441385.png

In [ ]:
from itertools import permutations

circuits1 = [
    ('Baku City Circuit', 'Baku', 'Azerbaijan', 40.3725, 49.853333),
    ('Bahrain International Circuit', 'Sakhir', 'Bahrain', 26.0325, 50.510556),
    ('Lusail International Circuit', 'Lusail', 'Qatar', 25.49, 51.454167),
    ('Yas Marina Circuit', 'Abu Dhabi', 'United Arab Emirates', 24.467222, 54.603056),
    ('Jeddah Corniche Circuit', 'Jeddah', 'Saudi Arabia', 21.631944, 39.104444),
    ('Marina Bay Street Circuit', 'Marina Bay', 'Singapore', 1.291531, 103.86385),
]

# Distancia recorrida actual de esos nodos
currentDistance = 0

for i in range(1, len(circuits1)):
    currentDistance += haversineDistance(circuits1[i-1], circuits1[i])

# Generar todos los posibles recorridos
array = [i for i in range(len(circuits1))]
perms = permutations(array)

# Solo se necesitan los recorridos que empiezan en Baku y terminan en Marina Bay
perms = list(filter(lambda i: i[0] == 0 and i[-1] == 5, perms))
print(f'Complejidad: {len(perms)} posibles soluciones\n')

# Hacer la búsqueda exhaustiva buscando la ruta más corta
bestDistance, bestRoute = float('inf'), []

for perm in perms:
    distance = 0

    for i in range(1, len(perm)):
        distance += haversineDistance(circuits1[perm[i-1]], circuits1[perm[i]])

    if distance < bestDistance:
        bestDistance, bestRoute = distance, perm

# Imprimir los resultados
print(f'Total recorrido actual: {round(currentDistance, 2)}Km')
print(f'Total recorrido óptimo: {round(bestDistance, 2)}Km')
print(f'Mejora con respecto al actual: {round(((currentDistance-bestDistance)/currentDistance)*100, 2)}%')

print('\nRuta:')
for i, city in enumerate(bestRoute):
    print(f'{i+16}. {circuits1[city][1]}, {circuits1[city][2]}')
Complejidad: 24 posibles soluciones

Total recorrido actual: 11014.56Km
Total recorrido óptimo: 9907.65Km
Mejora con respecto al actual: 10.05%

Ruta:
16. Baku, Azerbaijan
17. Jeddah, Saudi Arabia
18. Sakhir, Bahrain
19. Lusail, Qatar
20. Abu Dhabi, United Arab Emirates
21. Marina Bay, Singapore

Solución final¶

Aplicando las mejoras encontradas utilizando búsqueda exhaustiva se llega a la conclución de que el recorrido más óptimo para los 23 circuitos del calendario 2023 de la Formula 1 es:

  1. Sao Paulo, Brazil
  2. Miami, United States
  3. Mexico City, Mexico
  4. Austin, United States
  5. Las Vegas, United States
  6. Montreal, Canada
  7. Silverstone, United Kingdom
  8. Zandvoort, Netherlands
  9. Spa-Francorchamps, Belgium
  10. Barcelona, Spain
  11. Montecarlo, Monaco
  12. Monza, Italy
  13. Imola, Italy
  14. Spielberg, Austria
  15. Budapest, Hungary
  16. Baku, Azerbaijan
  17. Jeddah, Saudi Arabia
  18. Sakhir, Bahrain
  19. Lusail, Qatar
  20. Abu Dhabi, United Arab Emirates
  21. Marina Bay, Singapore
  22. Suzuka, Japan
  23. Melbourne, Australia

imagen_2023-06-21_231023146.png

Cabe aclarar que este orden puede darse de manera invesa, ya que las distancias recorridas son iguales y, Aunque no se tiene en cuenta en este trabajo, el orden inverso podría cumplir de mejor manera con otras resticciones en la realización de los Grandes Premios (Tales como cuestiones climáticas o religiosas)

In [ ]:
circuits = [
    ('Autódromo José Carlos Pace', 'Sao Paulo', 'Brazil', -23.701111, -46.697222),
    ('Miami International Autodrome', 'Miami', 'United States', 25.958056, -80.238889),
    ('Autódromo Hermanos Rodriguez', 'Mexico City', 'Mexico', 19.406111, -99.0925),
    ('Circuit of the Americas', 'Austin', 'United States', 30.132778, -97.641111),
    ('Las Vegas Strip Circuit', 'Las Vegas', 'United States', 36.119684, -115.172599),
    ('Circuit Gilles Villeneuve', 'Montreal', 'Canada', 45.500556, -73.5225),
    ('Silverstone Circuit', 'Silverstone', 'United Kingdom', 52.078611, -1.016944),
    ('Circuit Zandvoort', 'Zandvoort', 'Netherlands', 52.388819, 4.540922),
    ('Circuit de Spa-Francorchamps', 'Spa-Francorchamps', 'Belgium', 50.437222, 5.971389),
    ('Circuit de Barcelona-Catalunya', 'Barcelona', 'Spain', 41.57, 2.261111),
    ('Circuit de Monaco', 'Montecarlo', 'Monaco', 43.734722, 7.420556),
    ('Autodromo Nazionale di Monza', 'Monza', 'Italy', 45.620556, 9.289444),
    ('Autodromo Internazionale Enzo e Dino Ferrari', 'Imola', 'Italy', 44.341111, 11.713333),
    ('Red Bull Ring', 'Spielberg', 'Austria', 47.219722, 14.764722),
    ('Hungaroring', 'Budapest', 'Hungary', 47.582222, 19.251111),
    ('Baku City Circuit', 'Baku', 'Azerbaijan', 40.3725, 49.853333),
    ('Jeddah Corniche Circuit', 'Jeddah', 'Saudi Arabia', 21.631944, 39.104444),
    ('Bahrain International Circuit', 'Sakhir', 'Bahrain', 26.0325, 50.510556),
    ('Lusail International Circuit', 'Lusail', 'Qatar', 25.49, 51.454167),
    ('Yas Marina Circuit', 'Abu Dhabi', 'United Arab Emirates', 24.467222, 54.603056),
    ('Marina Bay Street Circuit', 'Marina Bay', 'Singapore', 1.291531, 103.86385),
    ('Suzuka International Racing Course', 'Suzuka', 'Japan', 34.843056, 136.540556),
    ('Albert Park Circuit', 'Melbourne', 'Australia', -37.849722, 144.968333),
]

# Distancia recorrida actual en kilometros
optimalKilometers = 0

for i in range(1, len(circuits)):
    optimalKilometers += haversineDistance(circuits[i-1], circuits[i])

# Resultados finales
print(f'Total recorrido actual: {round(currentTotalDistance, 2)} Km')
print(f'Total recorrido óptimo: {round(optimalKilometers, 2)} Km')
print(f'Mejora con respecto al actual: {round(((currentTotalDistance-optimalKilometers)/currentTotalDistance)*100, 2)}%')
Total recorrido actual: 132163.47 Km
Total recorrido óptimo: 49364.9 Km
Mejora con respecto al actual: 62.65%